package personal.leil.learning.exercises;

import personal.leil.learning.SNode;
import personal.leil.learning.utils.LinkedListUtils;

import java.util.Stack;

/**
 * 判断一个链表是否为回文结构
 * <p>
 * 1=>2=>3=>2=>1、1=>2=>3=>3=>2=>1
 * 额外空间复杂度不限
 * 栈
 * 额外空间复杂度O(1)
 * 快慢指针
 * </p>
 */
public class Question2 {


    /**
     * 不考虑额外空间复杂度的情况下，可以使用栈辅助反转链表进行比对
     *
     * @param head head for linked list
     * @return check result
     */
    public static boolean process1(SNode head) {
        Stack<SNode> stack = new Stack<>();
        SNode current = head;
        while (current != null) {
            stack.push(current);
            current = current.getNext();
        }
        current = head;
        boolean flag = true;
        while (current != null) {
            SNode tail = stack.pop();
            if ((int) current.getData() != (int) tail.getData()) {
                flag = false;
                break;
            }
            current = current.getNext();
        }
        return flag;
    }


    /**
     * 要求额外空间复杂度O(1)
     * <p>
     * 1、通过快慢指针找出链表中点位置 <br/>
     * 2、根据链表的奇偶性找到中点的位置 <br/>
     *   1）、奇数：快、慢指针同时指向链表头部，快指针一次走两步，慢指针一次走一步，快指针走完后，慢指针指向的节点为中点 <br/>
     *   2）、偶数：快、慢指针同时指向链表头部，快指针先走一步，然后快指针一次走两步，慢指针一次走一步，快指针走完后，慢指针指向中心对称轴的前一个位置 <br/>
     * 3、对称轴向右依次翻转，前半部分和后半部分比较 <br/>
     * 4、将后半部分链表恢复 <br/>
     * </p>
     *
     * @param head  head for linked list
     * @param isOdd odd-even of size for linked list
     * @return check result
     */
    public static boolean process2(SNode head, boolean isOdd) {
        SNode f = head;
        SNode s = isOdd ? head : head.getNext();
        while (f != null && f.getNext() != null && s != null) {
            f = f.getNext().getNext();
            s = s.getNext();
        }
        /*
         *后半部分反转
         */
        SNode reverseCurrent = s.getNext();
        SNode prev = null;
        while (reverseCurrent != null) {
            SNode next = reverseCurrent.getNext();
            reverseCurrent.setNext(prev);
            prev = reverseCurrent;
            reverseCurrent = next;
        }
        /*
         * 比对
         */
        SNode front = head;
        SNode back = prev;
        boolean flag = true;
        while (front != null && back != null) {
            if ((int) front.getData() != (int) back.getData()) {
                flag = false;
                break;
            }
            front = front.getNext();
            back = back.getNext();
        }
        /*
         * 再将后半部分恢复拼接到原链表上
         */
        SNode reverseCurrent1 = prev;
        SNode prev1 = null;
        while (reverseCurrent1 != null) {
            SNode next = reverseCurrent1.getNext();
            reverseCurrent1.setNext(prev1);
            prev1 = reverseCurrent1;
            reverseCurrent1 = next;
        }
        s.setNext(prev1);
        return flag;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        SNode head1 = LinkedListUtils.buildSingleLinkedList(new int[]{1, 2, 3, 4, 3, 2, 1});
        LinkedListUtils.printSingleLinkedList(head1);
        System.out.println("process for result:" + process2(head1, true));
        System.out.println("after process:");
        LinkedListUtils.printSingleLinkedList(head1);

        SNode head2 = LinkedListUtils.buildSingleLinkedList(new int[]{1, 2, 3, 3, 2, 1});
        LinkedListUtils.printSingleLinkedList(head2);
        System.out.println("process for result:" + process2(head2, false));
        System.out.println("after process:");
        LinkedListUtils.printSingleLinkedList(head2);
    }

}
